from collections import defaultdict
from typing import List


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        # 选 or 不选问题,每一个只能选一次
        ans = []
        path = []
        n = len(candidates)

        def dfs(i, cnt):

            if cnt == 0:
                ans.append(path.copy())
                return
            if i == n or cnt < 0:
                return

            # 不选当前数字，并跳过后续所有相同的数字
            j = i
            while j + 1 < n and candidates[j] == candidates[j + 1]:
                j += 1
            dfs(j + 1, cnt)
            # 选
            path.append(candidates[i])
            dfs(i + 1, cnt - candidates[i])
            path.pop()

        dfs(0, target)
        return ans


# 方法二：
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()

        ans = []
        path = []
        n = len(candidates)
        has=defaultdict(set)
        # 选哪一个
        def dfs(i, cnt):

            if cnt == 0:
                ans.append(path.copy())
                return
            if i == n or cnt < 0:
                return
            # 选哪一个问题
            for j in range(i, n):
                # 去重：跳过重复数字（避免重复组合） 1126
                if j > i and candidates[j] == candidates[j - 1]:
                    continue
                # 选 candidates[j]
                path.append(candidates[j])
                dfs(j + 1, cnt - candidates[j])
                path.pop()

        dfs(0, target)
        return ans


